﻿#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], pre[N], id, h;
int mp[N];
//头插
void push_front(int x)
{
	id++;
	e[id] = x;
	mp[x] = id;
	ne[id] = ne[h];
	pre[id] = h;
	pre[ne[h]] = id;
	ne[h] = id;
}
int find(int x)
{
	return mp[x];
}
void print()
{
	for (int i = ne[h]; i != 0; i = ne[i]) {
		cout << e[i] << " ";
	}
	cout << endl;
}
void insert(int p,int x)
{
	id++;;
	e[id] = x;
	ne[id] = ne[p];

	mp[x] = id;
	pre[id] = p;
	pre[ne[p]] = id;
	ne[p] = id;
}
int main()
{
	for (int i = 5; i>=0; i--)
	{
		push_front(i);
		print();
	}
	//cout << find(3) << endl;
	//cout << find(5) << endl;
	//cout << find(6) << endl;

	insert(2, 22);
	print();
	insert(4, 100);
	print();
}
////创建
//int e[N], ne[N], h, id;
//int mp[N]; //mp[i]表⽰i这个数存储的位置
////遍历链表
//void print()
//{
//	for (int i = ne[h]; i; i = ne[i])
//	{
//		cout << e[i] << " ";
//	}
//	cout << endl << endl;
//}
////头插
//void push_front(int x)
//{
//	id++;
//	e[id] = x;
//	mp[x] = id;//标记x存储的位置
//	//先让新结点指向头结点的下⼀个位置
//	//然后让头结点指向新来的结点
//	ne[id] = ne[h];
//	ne[h] = id;
//}
////按值查找
//int find(int x)
//{
//	//解法⼀：遍历链表
//	// 
//	// for(int i = ne[h]; i; i = ne[i])
//	// {
//	//     if (e[i] == x) return i;
//	// }
//	// return 0;
//	//解法二：用mp数组优化
//	return mp[x];
//}
////在任意位置p之后，插⼊⼀个新的元素x
//void insert(int p, int x)
//{
//	id++;
//	e[id] = x;
//	mp[x] = id;
//	ne[id] = ne[p];
//	ne[p] = id;
//}
////删除任意位置p后⾯的元素
//void erase(int p)
//{
//	if (ne[p]) //当p不是最后⼀个元素的时候
//	{
//		mp[e[ne[p]]] = 0; //把标记清空
//		ne[p] = ne[ne[p]];
//	}
//}
//int main()
//{
//	for (int i = 1; i <= 5; i++)
//	{
//		push_front(i);
//		print();
//	}
//	//cout << find(1) << endl;
//	//cout << find(5) << endl;
//	//cout << find(6) << endl;
//	// insert(1, 10);
//	// print();
//	// insert(2, 100);
//	// print();
//	erase(2);
//	print();
//	erase(4);
//	print();
//	return 0;
//}